#include"BinaryTree.h"
#include"Queue.h"
BTNode* BuyNode(char val)
{
	BTNode*	newnode=(BTNode*)malloc(sizeof(BTNode));
	if(newnode==NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->x=val;
	newnode->left=newnode->right=NULL;
	return newnode;
}
//前序遍历（根左右）
void preOrder(BTNode* root)
{
	if(root==NULL)
	{
		printf("NULL");
		return;
	}
	printf("%c  ",root->x);
	preOrder(root->left);
	preOrder(root->right);
}
//中序遍历（左根右）
void inOrder(BTNode* root)
{
	if(root==NULL)
	{
		printf("NULL");
		return;
	}
	inOrder(root->left);
	printf("%c  ",root->x);
	inOrder(root->right);
}
//后序遍历（左右根）
void postOrder(BTNode* root)
{
	if(root==NULL)
	{
		printf("NULL");
		return;
	}
	postOrder(root->left);
	postOrder(root->right);
	printf("%c  ",root->x);
}

// ⼆叉树结点个数 
int BinaryTreeSize(BTNode* root)
{
	if(root==NULL)
	{
		return 0;
	}
	return 1+BinaryTreeSize(root->left)+BinaryTreeSize(root->right);//注意不能自己调用自己
}




// ⼆叉树叶⼦结点个数 
int BinaryTreeLeafSize(BTNode* root)
{
	if(root==NULL)
	{
		return 0;
	}
	if(root->left==NULL&&root->right==NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->left)+BinaryTreeLeafSize(root->right);
}
// ⼆叉树第k层结点个数 
int BinaryTreeLevelKSize(BTNode* root, int k) 
{
	if(root==NULL)
	{
		return 0;
	}
	if(k==1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left,k-1)+BinaryTreeLevelKSize(root->right,k-1);
}
//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root)
{
	if(root==NULL)
	{
		return 0;
	}
	int leftdep=BinaryTreeDepth(root->left);
	int rightdep=BinaryTreeDepth(root->right);
	return 1+(leftdep>rightdep?leftdep:rightdep);
}
// ⼆叉树查找值为x的结点 ,思路相同，只是把遍历左右子树条件改了
BTNode* BinaryTreeFind(BTNode* root, BTDataType m)
{
	if(root==NULL)
	{
		return NULL;
	}
	if(root->x=m)
	{
		return root;
	}
	BTNode* left=BinaryTreeFind(root->left,m);
	if(left)
	{
		return left;
	}
	BTNode* right=BinaryTreeFind(root->right,m);
	if(right)
	{
		return right;
	}
	return NULL;
}

// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root)
{	
	if(*root==NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));
	free(*root);
	*root=NULL;
}

//层序遍历（借助队列）
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q,root);
	
	while(!QueueEmpty(&q))
	{
		//取队头出队头，打印结点值
		BTNode* top=QueueFront(&q);
		QueuePop(&q);
		printf("%c",top->x);
		//将队头非空左右孩子入队列
		if(top->left)
		{
			QueuePush(&q,top->left);
		}
		if(top->right)
		{
			QueuePush(&q,top->right);
		}

	}
	QueueDestroy(&q);
}
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q,root);
	while(!QueueEmpty(&q))
	{
		//取队头数据，直到遇到第一个NULL返回
		BTNode* top=QueueFront(&q);
		QueuePop(&q);
		if(top==NULL)
		{
			break;
		}
		QueuePush(&q,top->left);
		QueuePush(&q,top->right);
	}
	//队列出现非空节点，说明是非完全二叉树
	while(!QueueEmpty(&q))
	{
		BTNode* top=QueueFront(&q);
		QueuePop(&q);
		if(top)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	return true;
	QueueDestroy(&q);
}
bool isUnivalTree( BTNode* root)
{
	    if(!root)
    {
        return true;
    }
    if(root->left&&root->x!=root->left->x)
    {
        return false;
    }
    if(root->right&&root->x!=root->right->x)
    {
        return false;
    }
    return isUnivalTree(root->left)&&isUnivalTree(root->right);
}



bool isSameTree(BTNode* p, BTNode* q)
{
    //都为空
    if(p==NULL&&q==NULL)
    {
        return true;
    }
    //其中有一个为空
    if(p==NULL||q==NULL)
    {
        return false;
    }
    //都不为空
    if(p->x!=q->x)
    {
        return false;
    }
	return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}

bool isSymmetric(BTNode* root) 
{
	if(root==NULL)
	{
		return true;
	}
	BTNode* left=root->left;
	BTNode* right=root->right;
	//同相同二叉树比较
	if(left==NULL&&right==NULL)
	{
		return true;
	}
	if(left==NULL||right==NULL)
	{
		return false;

	}

	if(left->x!=right->x)
	{
		return false;
	}
	bool Helper(BTNode* a,BTNode*b)
	{
	if (a == NULL && b == NULL) return true;
	if (a == NULL || b == NULL) return false;
	if (a->x != b->x) return false;
	return Helper(a->left, b->right) && Helper(a->right, b->left);
}
	return Helper(left->left, right->right)&&Helper(left->right,right->left);
}


bool isSubtree(BTNode* root, BTNode* subRoot)
{
    if(root==NULL)
    {
        return false;
    }
    if(isSameTree(root,subRoot))
    {
        return true;
    }
    //不等于的时候继续走就行
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

BTNode* creatTree(char* arr,int* pi)
{
	if(arr[(*pi)]=='#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root=BuyNode(arr[(*pi)]);
	(*pi)++;
	root->left= creatTree(arr,pi);
	root->right= creatTree(arr,pi);
	return root;
}

void post(BTNode* root,int* arr,int* pi)
{
	if(root==NULL)
	{
		return;
	}
	post(root->left,arr,pi);
	post(root->right,arr,pi);
	arr[(*pi)]=root->x;
	(*pi)++;
}
int* postorderTraversal(BTNode* root, int* returnSize) 
{
	*returnSize=BinaryTreeSize(root);
	int* arr=(int*)malloc((*returnSize)*sizeof(int));
	if (arr == NULL)
	{
		*returnSize = 0;
		return NULL;
	}
	int i=0;
	post(root,arr,&i);
	return arr;	
}

